package com.topcoder.srm519;

import java.util.Comparator;
import java.util.PriorityQueue;

public class ThreeTeleports {
	public int shortestDistance(int xMe, int yMe, int xHome, int yHome, String[] teleports) {
		long[][] d = new long[8][8];
		Point[] p = new Point[8];
		p[0] = new Point(xMe, yMe);
		p[1] = new Point(xHome, yHome);
		for (int i=1; i<4; i++) {
			String[] str = teleports[i-1].split(" ");
			p[2*i] = new Point(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
			p[2*i+1] = new Point(Integer.parseInt(str[2]), Integer.parseInt(str[3]));
		}
		
		for (int i=0; i<8; i++) {
			for (int j=0; j<8; j++) {
				d[i][j] = Math.abs(p[i].x - p[j].x) + Math.abs(p[i].y - p[j].y);
			}
		}
		
		for (int i=1; i<4; i++) {
			d[2*i][2*i+1] = Math.min(d[2*i][2*i+1], 10);
			d[2*i+1][2*i] = Math.min(d[2*i+1][2*i], 10);
		}
		
//		return dijkstra(d);
		return floyd_warshall(d);
	}
	
	private int floyd_warshall(long[][] d) {
		for (int k=0; k<8; k++) {
			for (int i=0; i<8; i++) {
				for (int j=0; j<8; j++) {
					if (d[i][j] > d[i][k] + d[k][j]) {
						d[i][j] = d[i][k] + d[k][j];
					}
				}
			}
		}
		return (int) d[0][1];
	}
	
	private int dijkstra(long[][] d) {
		long[] c = new long[8];
		for (int i=0; i<8; i++) c[i] = Long.MAX_VALUE;
		c[0] = 0;
		
		PriorityQueue<Cost> pq = new PriorityQueue<Cost>(10, new Comparator<Cost>(){
			public int compare(Cost a, Cost b) {
				return (int)(a.distance - b.distance);
			}
		});
		pq.add(new Cost(0, 0));
		
		while (!pq.isEmpty()) {
			Cost cost = pq.remove();
			if (cost.i == 1) return (int) cost.distance;
			for (int j=1; j<8; j++) {
				if (c[j] > c[cost.i] + d[cost.i][j]) {
					c[j] = c[cost.i] + d[cost.i][j];
					pq.add(new Cost(j, c[j]));
				}
			}
		}
		
		return -1;
	}
	
	private class Cost {
		int i;
		long distance;
		public Cost(int i, long distance) {
			this.i = i;
			this.distance = distance;
		}
	}
	
	private class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}
